#include <iostream>
#include <vector>
using namespace std;
class Solution {
 public:
  vector<int> path;
  vector<vector<int> > res;
  vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    backtracking(candidates, candidates.size(), target, 0);
    return res;
  }
  void backtracking(vector<int>& candidates, int len, int target,
                    int start_index) {
    if (target == 0) {
      res.push_back(path);
      return;
    }
    for (int i = start_index; i < len && candidates[i] <= target; i++) {
      if (i > start_index && candidates[i] == candidates[i - 1]) continue;
      path.push_back(candidates[i]);
      backtracking(candidates, len, target - candidates[i],
                   i + 1);  // 不是start_index+1 ,是i + 1
      path.pop_back();
    }
  }
};